A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data in the comparand register. When the content stored in the CAM memory location does not match the data in the comparand register, the local match detection circuit returns a no match indication. When the content stored in the CAM memory location matches the data in the comparand register, a local match detection circuit returns a match indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address location in which the matched data is stored or one of such addresses if more than one address contained matching data. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
Locally, CAMs may perform match detection using an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number of stored bits may be simultaneously detected for a match with the input bits in the match detection circuit. One way in which this is achieved is by coupling a plurality of storage devices and logic circuits to a common Match line, as depicted in FIG. 1.
Turning to FIG. 1, a schematic diagram of a conventional match detection circuit 100 is depicted. A first source/drain terminal of a p-type pre-charge transistor 102 is coupled to a positive voltage source (e.g., VDD). The gate of transistor 102 is coupled to a signal line 138 for receiving a Pre-charge signal. A second source/drain terminal of transistor 102 is coupled to a Match line 140 for pre-charging the Match line 140 to a predetermined voltage level (e.g., VDD).
Respective outputs Q0, Q1, Qn-1 of storage elements 104, 114, 124, which are to be respectively compared with the input bits B0, B1, Bn-1 are respectively coupled to gates of n-type transistors 106, 116 and 126. First respective source/drain terminals of transistors 106, 116 and 126 are coupled to the Match line 140.
Second respective source/drain terminals of transistors 106, 116 and 126 are respectively coupled to n-type transistors 110, 120 and 130. Second respective source/drain terminals of transistors 110, 120 and 130 are coupled to ground. The gates of transistors 110, 120 and 130 are respectively coupled to complements B0′, B1′ and Bn-1′ of the respective input bits.
Further, the respective complements of the outputs Q0′, Q1′ and Qn-1′ of the storage elements 104, 114 and 124 are respectively coupled to gates of n-type transistors 108, 118 and 128. First respective source/drain terminals of transistors 108, 118 and 128 are coupled to the Match line 140. Second source/drain terminals of transistors 108, 118 and 128 are respectively coupled to first source/drain terminals of n-type transistors 112, 122 and 132. Second respective source/drain terminals of transistors 112, 122 and 132 are coupled to ground. The gates of transistors 112, 122 and 132 are respectively coupled to the input bits B0, B1 and Bn-1 to be respectively compared with the complements Q0′, Q1′ and Qn-1′ of the stored bits being stored in storage elements 104, 114 and 124.
Input bits B0, B1, and Bn-1 used to store information in the storage elements are also respectively coupled to first respective source/drain terminals of n-type transistors 162, 172, and 182. Second respective source/drain terminals of transistors 162, 172, and 182 are coupled to respective inputs of storage elements 104, 114, and 124. The gates of transistors 162, 172, and 182 are coupled to a word select line 190. The complement of input bits B0′, B1′, and Bn-1′ used to store information in the storage elements are respectively coupled to first respective source/drain terminals of n-type transistors 164, 174, and 184. Second respective source/drain terminals of transistors 164, 174, and 184 are coupled to respective inputs of storage elements 164, 174, and 184. The gates of transistors 164, 174, and 184 are coupled to a word select line 190.
Also coupled to the Match line 140 is a buffer 136 for buffering the Match line 140 voltage and for outputting the Match signal. A Match signal of logic HIGH (e.g., VDD) represents that an exact match was detected between the input bits B0, B1, Bn-1 and the stored bits Q0, Q1, Qn-1. A Match signal of logic LOW (e.g., Ground) represents that at least one bit of the stored bits did not match its corresponding input bit causing the Match line to be pulled to Ground. Capacitor 134 represents the parasitic capacitance of the Match line 140 that is pre-charged to the initial predetermined value (e.g., VDD).
To write to or to read from storage elements 104, 114, and 124, a word select signal is enabled Logic HIGH then Logic LOW which temporarily closes transistors 162, 164, 172, 174, 182, and 184 and couples the storage elements 104, 114, and 124 to their respective input bits B0, B1, and Bn-1 and the respective complement of input bits B0′, B1′, and Bn-1′.
During operation of the FIG. 1 match detection circuit 100, the Pre-charge signal goes logic LOW then logic HIGH in order to pre-charge the Match line 140 to VDD. The state of the stored bits Q0, Q1, Qn-1 stored by the respective storage elements 104, 114, 124 and their complements Q0′, Q1′, Qn-1′ are respectively coupled to the gates of n-type transistors 106, 116, 126, 108, 118, 128. Consequently, depending upon the states at their respective gates, the transistors 106, 116, 126, 108, 118, 128 may become active and conduct.
Similarly, the state of the input bits B0, B1, Bn-1 and their complements B0′, B1′, Bn-1′ are coupled to the gates of n-type transistors 112, 122, 132, 110, 120, 130. Consequently, depending upon the states at their respective gates, the transistors 112, 122, 132, 110, 120, 130 may become active and conduct. Consequently, input bits B0, B1, Bn-1 and their complements B0′, B1′, Bn-1′ serve in more than one capacity: they function to read and write information to the storage elements 104, 114, and 124 and they also function to carry the information stored in the comparand for comparison with information stored in the storage elements 104, 114, and 124.
When a match is detected, at least one transistor of each serially connected pair of transistors (e.g., 106 and 110, 108 and 112, etc.) is inactive and not conducting. Therefore, when the Match line 140 remains logic HIGH, this signifies to the outside world that a match has been detected and potentially enables any other functions desired when a match is detected (e.g., provide the user with the address of the memory location where the match was found, forward the data to another location, etc.).
However, when a mismatch is detected, as is most often the case during a search for a particular bit pattern, at least one pair of serially connected transistors (e.g., 106, 108, 110, and 112) is active and conducting and the Match line 140 is coupled to Ground. When the Match line 140 is coupled to Ground, the Match signal goes logic LOW and signifies to the outside world that a mismatch has been detected in this particular series of storage elements 104, 114, 124. Although match circuit 100 is shown with three storage elements 104, 114 and 124, any number of storage elements may be utilized.
In the above-identified search process, the searched data (i.e., the input bits from the comparand) present on the respective bit lines is simultaneously compared with every data word in the CAM 100 in order to find a match between the stored data and the input data. As seen in FIG. 2, a CAM search circuit 200 for use during a write operation is shown, which includes the CAM bank 210. A CAM bank 210 includes a plurality of match detection circuits 100 (FIG. 1). A database (not shown) which supplies the data words to be stored in storage elements 104, 114, and 124 (FIG. 1) of each match detection circuit 100 is coupled to the CAM bank 210.
FIG. 3 shows a CAM search circuit 201 for using in CAM during a read operation. The search circuit 201 encompasses the circuits used in search circuit 200 for using in CAM during a write operation (FIG. 2) and includes additional elements enabling a read access operation to a match detection circuit 100. As seen in FIG. 3, an address generator 218 is coupled to the CAM bank 210 which supplies the address corresponding to a respective data word. A comparand data register 202 which stores the information sought to be compared is coupled to CAM bank 210. The CAM bank 210 is also coupled to data read register 212 which is used to store data read from the CAM bank. The CAM bank 210 is also coupled to a priority encoder 214. The CAM search circuit 201 outputs the address of the word in the CAM bank 210 that matches the comparand. In a CAM bank 210 however, more than a single word may match the comparand, but the CAM search circuit 201 may need to indicate the address of only one of the matching words.
The priority encoder 214 is used in the CAM search circuit 201 as the means to translate the position of a matching word from match detection circuit 100, into a numerical address representing the location of that word. Typically, the priority encounter returns the higher priority address (e.g., the smaller address). The priority encoder 214 is typically also used to only translate the location of one word, and ignore all other simultaneously matching words. A typical priority encoder 214 is comprised of two blocks. The first block is called the “highest priority indicator,” and is followed by the “address encoder” block. In the initial state all the inputs are at a state of logic HIGH which is the inactive state, while all the outputs are in the inactive state of logic LOW. Whenever any input goes to the active state of logic LOW, the output associated with this input becomes active as well, and goes to the state of logic HIGH. Consequently, an active input also disables all the inputs above it in the chain, forcing their associated outputs to remain inactive (e.g., logic LOW). The bottom of the priority encoder has the highest priority, and the priority descends toward the top. Therefore, if any number of inputs are simultaneously active, the highest priority indicator will activate only the output associated with the highest priority active input, leaving all other outputs inactive, thus indicating the highest priority activity. Many methods are use to convert the output of the highest priority indicator into a numerical value. The simplest method is that of a look-up table. Depending on the implementation, different implementations can be used for determining priority can be implemented, e.g., a lowest priority address may be desired. The output of the priority encoder 214 is coupled to a register 216 which coupled to a downstream circuit.
Because of the architecture of the CAM search circuit 200 and the corresponding architecture of a match detection circuit 100, it is possible that a read or write to storage elements of the CAM within a match detection circuit 100 during an on going search operation will cause an erroneous match between the comparand and a stored word. One approach to solving this problem is to suspend a search operation while reading or writing to a match detection circuit 100. This approach is not highly desirable because it would lead to significant decreases in search processing time.
Therefore, it is desirable to be able to read and write to a CAM match detection circuit without suspending a search and without causing an erroneous search result.